public class Nk_JN {
    public class PalindromeList {
        public boolean chkPalindrome(ListNode A) {
            if(A == null) return true;
            ListNode fast = A;
            ListNode slow = A;
            while(fast != null&&fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            ListNode cur = slow.next;
            while(cur != null) {
                ListNode curN = cur.next;
                cur.next = slow;
                slow = cur;
                cur = curN;
            }
            while(A != slow) {
                if(A.val == slow.val) {
                    if(A.next == slow) {
                        return true;
                    }
                    A = A.next;
                    slow = slow.next;
                } else {
                    return false;
                }
            }
            return true;
        }
    }

    public static void main(String[] args) {

    }
}
